package algorithm;

import java.util.Arrays;

public class leetcode_1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int i=0;
        int len=nums.length;
        for(i=0;i<len&&k>0;++i){
            if(nums[i]<0){
                nums[i]*=-1;
                k--;
            }
            else break;
        }
        if(k>0){
            if(k%2==1) {
                if(i>0&&i<len){
                    if(nums[i]>nums[i-1]) nums[i-1]*=-1;
                    else{
                        nums[i]*=-1;
                    }
                }
                else if(i==0){
                    nums[i]*=-1;
                }
                else nums[i-1]*=-1;
            }
        }
        int sum=0;
        for(i=0;i<len;++i){
            sum+=nums[i];
        }
        return sum;
    }
}
